package main

import "fmt"

/*
记忆化搜索，递推公式（也叫状态转移），深度优先（代码看着从前面处理，实则是压栈到最后面，从最后面最底层的数据反向开始处理），识别边界（到达边界返回）
整体思维（递归函数本身就表示返回一个“子模块”的最终答案），递归函数的实现要和函数本身意义的定义要一致（一致才能得到“子模块”的最终答案值）
定义"递推公式起始值" F(x₁)=V₁ ，也就是递归公式初始化值，也就是边界值，也就是所有边界的初始值。有边界初始值才能到达边界后反向得出前面的递推公式的具体值！

最最关键的代码技巧：边界值处理（边界判断终止递归）这个判断代码要“最后补充上去”，一定不是写递推公式代码的时候提前就琢磨考虑边界代码是什么，这样做只会打乱写代码的逻辑！！！
综合：递归函数，一定是“最后补充边界代码处理”，中途只有递推公式“整体处理”代码体现，最后补一个边界处理！！
*/

/*

[NOIP2005] 采药
山洞里有 M 株不同的草药，采每一株都需要一些时间 t_i，每一株也有它自身的价值 v_i。给你一段时间 T，在这段时间里，你可以采到一些草药。让采到的草药的总价值最大。
*/

// 二元关系：药的编号 + 剩余时间 => 整体后续最大价值
var dp [100][1000]int
var tCost [100]int
var vals [100]int
var n int
var t int

func dfs(pos int, tLeft int) (maxVal int) {
	if dp[pos][tLeft] != -1 {
		return dp[pos][tLeft]
	}

	if pos == n+1 {
		return 0 //返回边界值“常量”，这里边界值是固定的0，如果是每种变量边界值都不一样，那么这里返回的就是dp[pos][tLeft]这种跟对应变量挂钩的初始常量值
	}

	dp[pos][tLeft] = 0
	var v1, v2 = -1, -1
	v1 = dfs(pos+1, tLeft)
	if tLeft >= tCost[pos] {
		v2 = vals[pos] + dfs(pos+1, tLeft-tCost[pos])
	}
	dp[pos][tLeft] = max(v1, v2)

	return dp[pos][tLeft]
}

func main() {
	fmt.Println("总数量？ 总时间？")
	_, err := fmt.Scanf("%d%d\n", &n, &t)
	if err != nil {
		panic(err)
	}
	fmt.Println("数量：", n, "时间：", t)
	for i := 1; i <= n; i++ {
		fmt.Println("价值? 时间？")
		_, err = fmt.Scanf("%d%d\n", &vals[i], &tCost[i])
		if err != nil {
			panic(err)
		}
	}
	for i := range dp {
		for j := range dp[i] {
			dp[i][j] = -1
		}
	}
	v := dfs(1, t)
	fmt.Println("最大价值：", v)
}
